001 /*
002 * CrochemoreLandauZivUkelsonLocalAlignment.java
003 *
004 * Copyright 2003 Sergio Anibal de Carvalho Junior
005 *
006 * This file is part of NeoBio.
007 *
008 * NeoBio is free software; you can redistribute it and/or modify it under the terms of
009 * the GNU General Public License as published by the Free Software Foundation; either
010 * version 2 of the License, or (at your option) any later version.
011 *
012 * NeoBio is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
013 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
014 * PURPOSE. See the GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License along with NeoBio;
017 * if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
018 * Boston, MA 02111-1307, USA.
019 *
020 * Proper attribution of the author as the source of the software would be appreciated.
021 *
022 * Sergio Anibal de Carvalho Junior mailto:sergioanibaljr@users.sourceforge.net
023 * Department of Computer Science http://www.dcs.kcl.ac.uk
024 * King's College London, UK http://www.kcl.ac.uk
025 *
026 * Please visit http://neobio.sourceforge.net
027 *
028 * This project was supervised by Professor Maxime Crochemore.
029 *
030 */
031
032 package neobio.alignment;
033
034 /**
035 * This class implements the <B>local</B> pairwise sequence alignment algorithm (with
036 * linear gap penalty function) due to Maxime Crochemore, Gad Landau and Michal
037 * Ziv-Ukelson (2002).
038 *
039 * <P>This implementation derives from the paper of M.Crochemore, G.Landau and
040 * M.Ziv-Ukelson, <I>A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Scoring
041 * Matrices</I> (available here as
042 * <A HREF="doc-files/Crochemore_Landau_Ziv-Ukelson_algorithm.pdf">PDF</A> or
043 * <A HREF="doc-files/Crochemore_Landau_Ziv-Ukelson_algorithm.pdf">Postscript</A>).</P>
044 *
045 * <P>For a general description of the algorithm, please refer to the specification of the
046 * abstract {@linkplain CrochemoreLandauZivUkelson} superclass.</P>
047 *
048 * <P>This class consist mainly of methods that:</P>
049 *
050 * <LU>
051 * <LI>create and compute all information of a block (see {@link #createBlock createBlock}
052 * and its variants);
053 * <LI>compute the output border of a block (see {@link #computeOutputBorder
054 * computeOutputBorder};
055 * <LI>locate the score of a high scoring global alignment in the block table (see {@link
056 * #locateScore locateScore};
057 * <LI>build an optimal global alignment from the information stored in the block table
058 * (see {@link #buildOptimalAlignment buildOptimalAlignment}.
059 * </LU>
060 *
061 * <P>This algorithm works essentially in the same way as the global alignment version.
062 * The main differences is that an aptimal path can either be contained entirely in a
063 * block (called <B>C-path</B>) or be a block-crossing path. A block-crossing path
064 * consists of a (possibly empty) <B>S-path</B> (a path that starts inside a block and
065 * ends in its output border), followed by any number of paths that cross a block from its
066 * input border to its output border, and ending in an <B>E-path</B> (a path that starts
067 * in the input border of a block and ends inside the block).</P>
068 *
069 * <P>Therefore, it is necessary to compute extra information to keep track of these
070 * possibilities. This is accomplished by using an instance of a {@linkplain
071 * LocalAlignmentBlock} (which extends the {@linkplain AlignmentBlock} class) for every
072 * block in the block table.</P>
073 *
074 * @see CrochemoreLandauZivUkelson
075 * @see CrochemoreLandauZivUkelsonLocalAlignment
076 * @author Sergio A. de Carvalho Jr.
077 */
078 public class CrochemoreLandauZivUkelsonLocalAlignment extends CrochemoreLandauZivUkelson
079 {
080 /**
081 * A constant that indicates that the best path ending at a given entry of the output
082 * border is a block-crossing path (one that starts outside the block).
083 */
084 protected static final byte TYPE_CROSSING_PATH = 0;
085
086 /**
087 * A constant that indicates that the best path ending at a given entry of the output
088 * border is a S-path (one that starts inside the block).
089 */
090 protected static final byte TYPE_S_PATH = 1;
091
092 /**
093 * A constant that indicates that the high scoring path ending in a given block is a
094 * C-path, i.e. one that starts inside the block.
095 */
096 protected static final byte TYPE_C_PATH = 2;
097
098 /**
099 * A constant that indicates that the high scoring path ending in a given block is an
100 * E-path, i.e. one that starts at its input border.
101 */
102 protected static final byte TYPE_E_PATH = 3;
103
104 /**
105 * The score of the high scoring local alignment found.
106 */
107 protected int max_score;
108
109 /**
110 * The row index of a block (in the block table) where the high scoring local
111 * alignment ends.
112 */
113 protected int max_row;
114
115 /**
116 * The column index of a block (in the block table) where the high scoring local
117 * alignment ends.
118 */
119 protected int max_col;
120
121 /**
122 * The type of the high scoring local alignment found.
123 */
124 protected byte max_path_type;
125
126 /**
127 * If the high scoring local alignment ends in an E-path at a block B, this field
128 * contains the index of the entry in the input border of B that where the E-path
129 * starts.
130 */
131 protected int max_source_index;
132
133 /**
134 * Creates and computes all information of an alignment block. This method works
135 * essentially in the same way as its global alignment counterpart. Its main job is to
136 * compute the DIST column for the block. It then request the
137 * <CODE>computeOutputBorder</CODE> method to compute the block's output border. It
138 * also computes all S, C and E-paths of this block. Finally, it checks if the C-path
139 * of this block is higher than the highest score found so far.
140 *
141 * @param factor1 factor of the first sequence
142 * @param factor2 factor of the second sequence
143 * @param row row index of the block in the block table
144 * @param col column index of the block in the block table
145 * @return the computed block
146 * @throws IncompatibleScoringSchemeException if the scoring scheme is not compatible
147 * with the sequences being aligned
148 */
149 protected AlignmentBlock createBlock (Factor factor1, Factor factor2, int row,
150 int col) throws IncompatibleScoringSchemeException
151 {
152 LocalAlignmentBlock block, left_prefix, diag_prefix, top_prefix;
153 int size, lr, lc, max, ins_E, del_E;
154 int score_ins, score_sub, score_del, ins, del, sub;
155
156 lr = factor1.length();
157 lc = factor2.length();
158 size = lr + lc + 1;
159
160 block = new LocalAlignmentBlock (factor1, factor2, size);
161
162 // retrieve pointers to prefixes
163 left_prefix = (LocalAlignmentBlock) getLeftPrefix (block);
164 diag_prefix = (LocalAlignmentBlock) getDiagonalPrefix (block);
165 top_prefix = (LocalAlignmentBlock) getTopPrefix (block);
166
167 // compute scores
168 score_ins = scoreInsertion (factor2.getNewChar());
169 score_sub = scoreSubstitution (factor1.getNewChar(), factor2.getNewChar());
170 score_del = scoreDeletion (factor1.getNewChar());
171
172 // compute block's data
173 for (int i = 0; i < size; i++)
174 {
175 ins = sub = del = ins_E = del_E = Integer.MIN_VALUE;
176
177 if (i < size - 1)
178 {
179 ins = left_prefix.dist_column[i] + score_ins;
180 ins_E = left_prefix.E_path_score[i];
181 }
182
183 if ((i > 0) && (i < size - 1))
184 {
185 sub = diag_prefix.dist_column[i - 1] + score_sub;
186 }
187
188 if (i > 0)
189 {
190 del = top_prefix.dist_column[i - 1] + score_del;
191 del_E = top_prefix.E_path_score[i - 1];
192 }
193
194 block.dist_column[i] = max = max (ins, sub, del);
195
196 if (max == ins)
197 block.direction[i] = LEFT_DIRECTION;
198 else if (max == sub)
199 block.direction[i] = DIAGONAL_DIRECTION;
200 else
201 block.direction[i] = TOP_DIRECTION;
202
203 block.E_path_score[i] = max = max (ins_E, block.dist_column[i], del_E);
204
205 if (max == ins_E)
206 {
207 block.E_path_ancestor[i] = left_prefix.E_path_ancestor[i];
208 block.E_path_ancestor_index[i] = left_prefix.E_path_ancestor_index[i];
209 }
210 else if (max == block.dist_column[i])
211 {
212 block.E_path_ancestor[i] = block;
213 block.E_path_ancestor_index[i] = i;
214 }
215 else
216 {
217 block.E_path_ancestor[i] = top_prefix.E_path_ancestor[i - 1];
218 block.E_path_ancestor_index[i] = top_prefix.E_path_ancestor_index[i - 1];
219 }
220
221 if (i < lc)
222 {
223 block.S_path_score[i] = left_prefix.S_path_score[i];
224 }
225 else if (i == lc)
226 {
227 ins = left_prefix.S_path_score[i-1] + score_ins;
228 sub = diag_prefix.S_path_score[i-1] + score_sub;
229 del = top_prefix.S_path_score[i] + score_del;
230
231 block.S_path_score[i] = max = max (0, ins, sub, del);
232
233 if (max == ins)
234 block.S_direction = LEFT_DIRECTION;
235 else if (max == sub)
236 block.S_direction = DIAGONAL_DIRECTION;
237 else if (max == del)
238 block.S_direction = TOP_DIRECTION;
239 else
240 block.S_direction = STOP_DIRECTION;
241 }
242 else
243 {
244 block.S_path_score[i] = top_prefix.S_path_score[i - 1];
245 }
246 }
247
248 computeOutputBorder (block, row, col, size, lc, lr);
249
250 ins = left_prefix.C;
251 del = top_prefix.C;
252 block.C = max = max (ins, block.S_path_score[lc], del);
253
254 if (block.C > max_score)
255 {
256 // assert block.C == block.S_path_score[lc]; => always true
257 max_score = block.C;
258 max_row = row;
259 max_col = col;
260 max_path_type = TYPE_C_PATH;
261 }
262
263 return block;
264 }
265
266 /**
267 * Creates the root block. This is a special case of the <CODE>createBlock</CODE>
268 * method. No information is actually computed.
269 *
270 * @param factor1 factor of the first sequence
271 * @param factor2 factor of the second sequence
272 * @return the root block
273 */
274 protected AlignmentBlock createRootBlock (Factor factor1, Factor factor2)
275 {
276 // resets the variables that keep track
277 // of the high scoring alignment
278 max_row = max_col = max_score = 0;
279 max_path_type = TYPE_C_PATH;
280
281 return new LocalAlignmentBlock (factor1, factor2);
282 }
283
284 /**
285 * Creates and computes all information of an alignment block of the first column of
286 * the block table. This is a special case of the <CODE>createBlock</CODE> method.
287 *
288 * @param factor1 factor of the first sequence
289 * @param factor2 factor of the second sequence
290 * @param col column index of the block in the block table
291 * @return the computed block
292 * @throws IncompatibleScoringSchemeException if the scoring scheme is not compatible
293 * with the sequences being aligned
294 * @see #createBlock createBlock
295 */
296 protected AlignmentBlock createFirstRowBlock (Factor factor1, Factor factor2, int col)
297 throws IncompatibleScoringSchemeException
298 {
299 LocalAlignmentBlock block, left_prefix;
300 int size, lr, lc, score_ins;
301
302 lr = 0; // factor1.length();
303 lc = factor2.length();
304 size = lr + lc + 1;
305
306 block = new LocalAlignmentBlock (factor1, factor2, size);
307
308 // retrieve a pointer to left prefix
309 left_prefix = (LocalAlignmentBlock) getLeftPrefix (block);
310
311 // compute insertion's score
312 score_ins = scoreInsertion (factor2.getNewChar());
313
314 // compute block's data
315 for (int i = 0; i < lc; i++)
316 {
317 block.dist_column[i] = left_prefix.dist_column[i] + score_ins;
318 block.direction[i] = LEFT_DIRECTION;
319 block.S_path_score[i] = left_prefix.S_path_score[i];
320
321 block.E_path_score[i] = left_prefix.E_path_score[i];
322 block.E_path_ancestor[i] = left_prefix.E_path_ancestor[i];
323 block.E_path_ancestor_index[i] = left_prefix.E_path_ancestor_index[i];
324 if (block.dist_column[i] > block.E_path_score[i])
325 {
326 block.E_path_score[i] = block.dist_column[i];
327 block.E_path_ancestor[i] = block;
328 block.E_path_ancestor_index[i] = i;
329 }
330 }
331
332 // last position
333 block.E_path_score[lc] = block.dist_column[lc] = 0;
334 block.direction[lc] = STOP_DIRECTION;
335
336 block.E_path_ancestor[lc] = block;
337 block.E_path_ancestor_index[lc] = lc;
338
339 block.S_direction = LEFT_DIRECTION;
340 block.S_path_score[lc] = left_prefix.S_path_score[lc - 1] + score_ins;
341 if (block.S_path_score[lc] <= 0)
342 {
343 block.S_path_score[lc] = 0;
344 block.S_direction = STOP_DIRECTION;
345 }
346
347 computeOutputBorder (block, 0, col, size, lc, lr);
348
349 block.C = max (left_prefix.C, block.S_path_score[lc]);
350
351 if (block.C > max_score)
352 {
353 max_score = block.C;
354 max_row = 0;
355 max_col = col;
356 max_path_type = TYPE_C_PATH;
357 }
358
359 return block;
360 }
361
362 /**
363 * Creates and computes all information of an alignment block of the first column of
364 * the block table. This is a special case of the <CODE>createBlock</CODE> method.
365 *
366 * @param factor1 factor of the first sequence
367 * @param factor2 factor of the second sequence
368 * @param row row index of the block in the block table
369 * @return the computed block
370 * @throws IncompatibleScoringSchemeException if the scoring scheme is not compatible
371 * with the sequences being aligned
372 * @see #createBlock createBlock
373 */
374 protected AlignmentBlock createFirstColumnBlock (Factor factor1, Factor factor2,
375 int row) throws IncompatibleScoringSchemeException
376 {
377 LocalAlignmentBlock block, top_prefix;
378 int size, lr, lc, score_del;
379
380 lr = factor1.length();
381 lc = 0; // factor2.length();
382 size = lr + lc + 1;
383
384 block = new LocalAlignmentBlock (factor1, factor2, size);
385
386 // retrieve a pointer to top prefix
387 top_prefix = (LocalAlignmentBlock) getTopPrefix (block);
388
389 // compute deletion's score
390 score_del = scoreDeletion (factor1.getNewChar());
391
392 // first position
393 block.E_path_score[0] = block.dist_column[0] = 0;
394 block.direction[0] = STOP_DIRECTION;
395
396 block.E_path_ancestor[0] = block;
397 block.E_path_ancestor_index[0] = 0;
398
399 block.S_direction = TOP_DIRECTION;
400 block.S_path_score[0] = top_prefix.S_path_score[0] + score_del;
401 if (block.S_path_score[0] <= 0)
402 {
403 block.S_path_score[0] = 0;
404 block.S_direction = STOP_DIRECTION;
405 }
406
407 // compute block's data
408 for (int i = 1; i < size; i++)
409 {
410 block.dist_column[i] = top_prefix.dist_column[i - 1] + score_del;
411 block.direction[i] = TOP_DIRECTION;
412 block.S_path_score[i] = top_prefix.S_path_score[i - 1];
413
414 block.E_path_score[i] = top_prefix.E_path_score[i - 1];
415 block.E_path_ancestor[i] = top_prefix.E_path_ancestor[i - 1];
416 block.E_path_ancestor_index[i] = top_prefix.E_path_ancestor_index[i - 1];
417 if (block.dist_column[i] > block.E_path_score[i])
418 {
419 block.E_path_score[i] = block.dist_column[i];
420 block.E_path_ancestor[i] = block;
421 block.E_path_ancestor_index[i] = i;
422 }
423 }
424
425 computeOutputBorder (block, row, 0, size, lc, lr);
426
427 block.C = max (block.S_path_score[lc], top_prefix.C);
428
429 if (block.C > max_score)
430 {
431 max_score = block.C;
432 max_row = row;
433 max_col = 0;
434 max_path_type = TYPE_C_PATH;
435 }
436
437 return block;
438 }
439
440 /**
441 * Computes the output border of a block. This method works essentially in the same
442 * way as its global alignment counterpart:
443 *
444 * <LU>
445 * <LI>Retrieve the block's input border;
446 * <LI>Retrieve the block's complete DIST matrix;
447 * <LI>Create an interface to the {@linkplain OutMatrix OUT} matrix from the input
448 * border and DIST matrix;
449 * <LI>Use {@linkplain Smawk SMAWK} to compute all column maxima of the OUT matrix
450 * (SMAWK finds the index of the row that contains the maximum value of a column);
451 * <LI>Assemble the output border by extracting the maximum values of each column of
452 * the OUT matrix using the information obtained in the previous step.
453 * </LU>
454 *
455 * <P>However, it also check if there is a better path starting inside the block (an
456 * S path) and oupdate the output border accordingly. It also checks if this block has
457 * any path of score higher than the maximum score found so far.
458 *
459 * @param block the block for which the output border is to be computed
460 * @param row row index of the block in the block table
461 * @param col column index of the block in the block table
462 * @param dim dimension of the output border
463 * @param lc number of columns of the block
464 * @param lr number of row of the block
465 */
466 protected void computeOutputBorder (LocalAlignmentBlock block, int row, int col, int
467 dim, int lc, int lr)
468 {
469 int[] input = assembleInputBorder (dim, row, col, lr);
470
471 int[][] dist = assembleDistMatrix (block, dim, row, col, lc); // (AlignmentBlock)
472
473 // build an interface to the OUT matrix
474 out_matrix.setData (dist, input, dim, lc);
475
476 // compute source_path using SMAWK
477 smawk.computeColumnMaxima(out_matrix, block.source_path);
478
479 // update output border
480 for (int i = 0; i < dim; i++)
481 {
482 block.path_type[i] = TYPE_CROSSING_PATH;
483 block.output_border[i] = out_matrix.valueAt(block.source_path[i], i);
484
485 // check if there is a better path starting inside the block
486 // (if there is a path of equal score, preference is given
487 // to the S-path because it ends sooner)
488 if (block.S_path_score[i] >= block.output_border[i])
489 {
490 block.output_border[i] = block.S_path_score[i];
491 block.path_type[i] = TYPE_S_PATH;
492 }
493
494 // check if this block contains a score higher
495 // than the best path found so far
496 if (input[i] + block.E_path_score[i] > max_score)
497 {
498 max_score = input[i] + block.E_path_score[i];
499 max_row = row;
500 max_col = col;
501 max_source_index = i;
502 max_path_type = TYPE_E_PATH;
503 }
504 }
505 }
506
507 /**
508 * Builds an optimal local alignment between the loaded sequences after the block
509 * table has been computed by tracing a path back in the block table.
510 *
511 * @return an optimal global alignment
512 * @throws IncompatibleScoringSchemeException If the scoring scheme is not compatible
513 * with the loaded sequences.
514 * @see CrochemoreLandauZivUkelson#traverseBlock
515 */
516 protected PairwiseAlignment buildOptimalAlignment ()
517 throws IncompatibleScoringSchemeException
518 {
519 LocalAlignmentBlock block;
520 StringBuffer gapped_seq1, tag_line, gapped_seq2;
521
522 gapped_seq1 = new StringBuffer();
523 tag_line = new StringBuffer();
524 gapped_seq2 = new StringBuffer();
525
526 block = (LocalAlignmentBlock) block_table[max_row][max_col];
527
528 if (max_path_type == TYPE_C_PATH)
529 {
530 // a C-path is essentially an S-path
531 traverseS_Path (block, gapped_seq1, tag_line, gapped_seq2);
532 }
533 else
534 {
535 traverseBlockCrossingPath (block, gapped_seq1, tag_line, gapped_seq2);
536 }
537
538 return new PairwiseAlignment (gapped_seq1.toString(), tag_line.toString(),
539 gapped_seq2.toString(), locateScore());
540 }
541
542 /**
543 * Traverses a series of block crossing paths to retrieve an optimal alignment. A
544 * block-crossing path consists of a (possibly empty) <B>S-path</B> (a path that
545 * starts inside a block and ends in its output border), followed by any number of
546 * paths that cross a block from its input border to its output border, and ending in
547 * an <B>E-path</B> (a path that starts in the input border of a block and ends inside
548 * the block).
549 *
550 * @param block the block to be traversed
551 * @param gapped_seq1 the StringBuffer to where the gapped sequence 1 is written to
552 * @param tag_line the StringBuffer to where the tag_line is written to
553 * @param gapped_seq2 the StringBuffer to where the gapped sequence 2 is written to
554 * @throws IncompatibleScoringSchemeException If the scoring scheme is not compatible
555 * with the loaded sequences.
556 */
557 protected void traverseBlockCrossingPath (LocalAlignmentBlock block,
558 StringBuffer gapped_seq1, StringBuffer tag_line, StringBuffer gapped_seq2)
559 throws IncompatibleScoringSchemeException
560 {
561 LocalAlignmentBlock ancestor;
562 int source, dest, ancestor_source;
563 int row, col;
564
565 row = max_row;
566 col = max_col;
567
568 // recover the E-path
569 source = max_source_index;
570 ancestor = block.E_path_ancestor[source];
571 ancestor_source = block.E_path_ancestor_index[source];
572 traverseBlock (ancestor, ancestor_source, gapped_seq1, tag_line, gapped_seq2);
573
574 // now recover crossing paths
575 while (true)
576 {
577 if (row == 0)
578 {
579 col = col - 1;
580 dest = block_table[row][col].factor2.length();
581 }
582 else if (col == 0)
583 {
584 row = row - 1;
585 dest = 0;
586 }
587 else
588 {
589 if (source < block.factor1.length())
590 {
591 col = col - 1;
592 dest = block_table[row][col].factor2.length() + source;
593 }
594 else if (source == block.factor1.length())
595 {
596 row = row - 1; col = col - 1;
597 dest = block_table[row][col].factor2.length();
598 }
599 else
600 {
601 row = row - 1;
602 dest = source - block.factor1.length();
603 }
604 }
605
606 // check if has reached the root block
607 if (!(row > 0 || col > 0)) break;
608
609 block = (LocalAlignmentBlock) block_table[row][col];
610
611 if (block.path_type[dest] == TYPE_S_PATH)
612 {
613 // last part, an S-path, and we're done
614 ancestor = (LocalAlignmentBlock) block.ancestor[dest];
615 traverseS_Path (ancestor, gapped_seq1, tag_line, gapped_seq2);
616 break;
617 }
618
619 source = block.source_path[dest];
620 ancestor = (LocalAlignmentBlock) block.ancestor[dest];
621 ancestor_source = source;
622
623 if (dest > block.factor2.length())
624 ancestor_source -= (block.factor1.length() - ancestor.factor1.length());
625
626 traverseBlock (ancestor, ancestor_source, gapped_seq1, tag_line, gapped_seq2);
627 }
628 }
629
630 /**
631 * Traverses an S-path of a block to retrieve a part of an optimal alignment from the
632 * new vertex of a block to entry in its input border. This method is essentially
633 * similar to the <CODE>traverseBlock</CODE>. The only difference is that it uses
634 * the information of the <CODE>S_direction field</CODE> of the
635 * <CODE>LocalAlignmentBlock</CODE> class.
636 *
637 * @param block the block to be traversed
638 * @param gapped_seq1 the StringBuffer to where the gapped sequence 1 is written to
639 * @param tag_line the StringBuffer to where the tag_line is written to
640 * @param gapped_seq2 the StringBuffer to where the gapped sequence 2 is written to
641 * @throws IncompatibleScoringSchemeException If the scoring scheme is not compatible
642 * with the loaded sequences.
643 */
644 protected void traverseS_Path (LocalAlignmentBlock block, StringBuffer gapped_seq1,
645 StringBuffer tag_line, StringBuffer gapped_seq2)
646 throws IncompatibleScoringSchemeException
647 {
648 char char1, char2;
649
650 while (block.S_direction != STOP_DIRECTION)
651 {
652 char1 = block.factor1.getNewChar();
653 char2 = block.factor2.getNewChar();
654
655 switch (block.S_direction)
656 {
657 case LEFT_DIRECTION:
658 gapped_seq1.insert (0, GAP_CHARACTER);
659 tag_line.insert (0, GAP_TAG);
660 gapped_seq2.insert (0, char2);
661
662 block = (LocalAlignmentBlock) getLeftPrefix (block);
663 break;
664
665 case DIAGONAL_DIRECTION:
666 gapped_seq1.insert (0, char1);
667 if (char1 == char2)
668 if (useMatchTag())
669 tag_line.insert (0, MATCH_TAG);
670 else
671 tag_line.insert (0, char1);
672 else if (scoreSubstitution(char1, char2) > 0)
673 tag_line.insert (0, APPROXIMATE_MATCH_TAG);
674 else
675 tag_line.insert (0, MISMATCH_TAG);
676 gapped_seq2.insert(0, char2);
677
678 block = (LocalAlignmentBlock) getDiagonalPrefix (block);
679 break;
680
681 case TOP_DIRECTION:
682 gapped_seq1.insert (0, char1);
683 tag_line.insert (0, GAP_TAG);
684 gapped_seq2.insert (0, GAP_CHARACTER);
685
686 block = (LocalAlignmentBlock) getTopPrefix (block);
687 break;
688 }
689 }
690 }
691
692 /**
693 * Returns the score of the high scoring local alignment in the block table.
694 *
695 * @return the score of the highest scoring local alignment
696 */
697 protected int locateScore ()
698 {
699 return max_score;
700 }
701 }